The present invention relates to a fuzzy logic system and method for applying fuzzy logic rules to a vector of signals, and more particularly, to a fuzzy logic system and method which uses the vector of signals to access a location in a rule partition table containing a list of only those rules which will produce non-zero outputs when applied to the particular vector of signals.
Logic systems have traditionally relied on the use of Boolean algebra. Boolean algebra uses variables which may take on either of the values TRUE and FALSE. These variables, when used in conjunction with Boolean operators, such as AND, OR, and NOT, form expressions which also take on either of the values TRUE and FALSE.
One application for Boolean algebra is in the design of expert systems. Such systems may be used to make real-time decisions for controlling a particular machine, or they may be tailored to simply provide answers, based on information stored in a knowledge base, to questions posed by a user. Determining these answers usually requires the expert system to make deductions and inferences from the information provided by the user before an appropriate answer can be retrieved from the knowledge base.
Boolean-based expert systems are typically composed of a collection of production rules that take the form "IF x, THEN y" (where the variable x may represent a boolean expression, such as x=a OR b). These systems tend to be very rigid due to the inherent on-off quality associated with their binary logic variables and rules. They do not deal well with concepts for which precise definitions are not available, such as whether something is "warm," "tall" or "bright." Furthermore, these systems also have trouble operating under conditions in which conflicting rules may be activated simultaneously.
To avoid these deficiencies, some expert systems use production rules in which boolean logic expressions are replaced by fuzzy logic expressions. Multi-valued logic systems were first proposed by the polish logician Jan Lukasiewicz in the 1920's. Fuzzy systems were later popularized by Lotfi Zadeh in the 1960's, who developed the concept of fuzzy set theory. Fuzzy logic variables make up for the imprecision associated with the traditional "on/off" characteristic of Boolean variables by representing each variable as a proportion of membership in related fuzzy sets (called membership elements). Therefore, it is possible for a variable with a given value to be a partial member of two or more fuzzy category labels at the same time (i.e. a room's temperature could be both hot and warm at the same time). This flexibility allows the fuzzy system to better model the ambiguity inherent in real world problems.
Fuzzy logic is now in use in embedded controllers in a number of commercial products, mainly from Japan. These fuzzy controllers have been described as easier and faster to design, and require less code than conventional methods. Fuzzy logic can be used to construct a fuzzy logic controller, or an expert system that can deal with uncertain reasoning, thus providing a significant advantage over conventional Artificial Intelligence (AI) techniques.
In addition, there is a direct relationship between fuzzy logic systems and feed foreword neural nets. This implies that a trained neural net can be represented as a fuzzy logic system, and vice versa. A fuzzy logic system could be used as an alternate implementation of a neural net trained for some specific task.
The flexibility of fuzzy systems is illustrated by the following example, in which each input and output variable to the fuzzy logic system is called a category, and in which each category is composed of a series of fuzzy identifiers called membership elements.
Referring now to FIG. 1, a fuzzy input category representing room temperature is shown. A fuzzy input category such as this may be used, for example, in a fuzzy heating controller. In this example, one input variable may be a measure of room temperature, in degrees Fahrenheit. The fuzzy membership elements associated with room temperature are defined to be the following:
VL=very low, L=low, M=medium, H=high, VH=very high.
The diagram in FIG. 1 shows the five fuzzy membership elements and their associated overlapping membership envelopes. The horizontal axis of the graph represents the category input value, which in this example is room temperature. The vertical axis represents the proportion of membership of a given input value in a particular membership element. Each membership element has an associated membership envelope which defines the proportion of membership in the membership element over the range of input values of the category. Before a fuzzy system can perform its processing with any category input value, that input value must be converted to a set of proportions of membership in corresponding membership elements. These will be referred to here as "fuzzy variables."
As can be seen from the figure, a particular category input value can be a member of more then one element, usually with different proportions for each membership element. For example, FIG. 1 illustrates a situation in which a room temperature category value of 70 degrees is a 60% member of the medium fuzzy membership element and a 40% member of the high fuzzy membership element.
It is important not to confuse proportions of membership with probabilities. A probability is a measure of how likely it is that something will occur. In contrast, fuzzy proportion of membership measures the extent to which something occurs. For example, the weather forecast statement "There will be a 60% chance of sun" provides information about the likelihood of having a clear day. By comparison, the fuzzy statement "There is 60% sun today" is a measure of how much the sun is shining, not whether it will shine. Note that in this case, it may simultaneously be true that it is 40% cloudy. Boolean-based systems, by contrast, might have trouble dealing with the variables "sunny" and "cloudy" both being true at the same time.
Just as standard expert systems typically comprise a collection of boolean algebra-based production rules, expert systems based on fuzzy logic utilize a set of fuzzy logic rules. Fuzzy logic rules take the same form as standard Boolean logic rules (i.e., "IF x THEN y"), but they use fuzzy set theory rather then binary logic. Fuzzy logical Intersection (X AND Y) is typically defined as the minimum of x and y, expressed as Min(x,y). Fuzzy logical Union (X OR Y) is typically defined as the maximum of x and y, expressed as Max(x,y). Fuzzy logical Negation of X is typically computed as (1-X). These definitions are the ones originally proposed by Zadeh. Alternative definitions also exist, and would be equally applicable in this discussion.
A conventional fuzzy system, then, functions by first converting "real world" input variables (such as "temperature=68.degree.") into fuzzy input variables (such as "temperature=70% warm, 30% cool, 0% cold, . . . "), and then applying each rule in the rule base to the fuzzy input variables to produce the fuzzy output variables (such as "fan speed=76% fast, 24% medium, 0% slow, . . . ") defined by the rule base. Finally, the fuzzy output variables, which are in the form of membership curves, must usually be converted back into a single numerical value (such as "fan speed=550 revolutions per minute") so that useful control signals can be generated. This "defuzzification" is commonly performed by the "centroid method." In this well known technique, the numerical output value is set equal to the computed center of mass, or centroid, of the area under the curve. Other defuzzification techniques are also available, but not as commonly used. Fuzzy input variables, fuzzy rules, and conversion of fuzzy variables into single numerical values are discussed in B. Kosko and S. Isaka, "Fuzzy Logic," SCIENTIFIC AMERICAN, pp 76-81, July 1993, which is hereby incorporated by reference.
A completely specified fuzzy rule system has, for each fuzzy output variable, a rule for each potential combination of input membership elements. As an example, consider a system that is composed of a number of input categories and one output category. For this example, suppose that each category (both input and output) has five fuzzy membership elements associated with it, as illustrated in FIG. 1.
If the fuzzy system has two input categories and one output category, then 5.times.5=25 rules are required for complete specification. Three input categories require 5.times.5.times.5=125 rules for complete specification. Five input categories require 5.times.5.times.5.times.5.times.5=3125 rules for complete specification. Thus, the number of fuzzy rules necessary to completely specify operation of the system grows exponentially as the number of system variables increases.
It is obvious that as the number of required input categories increases, the execution time associated with individual rules quickly becomes the dominant factor in the overall fuzzy system execution cycle.
One proposed solution to this problem is the construction of special purpose Very Large Scale Integrated Circuits (VLSI) fuzzy logic processors having hardware that is specially tailored for performing fuzzy computations at high speed. For example, VLSI Technology, Inc., of San Jose, Calif. manufactures the VY86C500, which is a 12-bit fuzzy computational acceleration core. Computational engines such as these allow thousands of fuzzy rules to be executed per second. However, it is desirable to find solutions which don't rely on brute-force computational power, so that fuzzy logic toolbox functionality can be implemented on conventional personal computer architectures.